Methods, devices, and articles of manufacture consistent with the present disclosure relate to a multiplication method and modular multiplier using redundant form recoding.
Representative examples of public key encryption algorithms are Rivest, Shamir, and Adleman (RSA) and ecliptic curve cryptosystem (ECC). RSA is based on a difficulty of an integer factorization problem, and ECC is based on a difficulty of an elliptic curve discrete logarithm problem (ECDLP). One of the most basic operations for implementing the RSA or ECC is a modular operation. The performance of the RSA or ECC may be influenced by a modular arithmetic unit that implements the modular operation. That is, as the performance of the modular arithmetic unit increases, the performance of the RSA or ECC based on the modular operation may be improved.